In recent years, public/private-key cryptosystems have been widely used for protection of commercial data transmitted via the Internet. In addition to their use in encrypting and decrypting messages, they are used in creating and verifying digital signatures and for key exchanges. Public/private-key variants include the Rivest-Shamir-Adleman (RSA) and the EIGamal cryptosystems. The RSA cryptosystem is described in U.S. Pat. No. 4,405,829.
Based on standard RSA and EIGamal algorithms, a variety of extensions have been constructed. Threshold cryptography addresses single-secret sharing and related function sharing for multiple players. Chaum developed a blind signature scheme to allow one party to get a message signed by another party without leaking information about the content of the message to the other party (D. Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM 28 (10, pp. 1030-1044, 1985.).
The RSA is a well-known and widely-used public key cryptosystem. The security of RSA is based on the intractability of the integer factorization problem. The key generation algorithm for RSA public key encryption is performed as follows:
1. Generate two large prime number p and q, each with roughly the same size (at least 100 digits). Let n=pq.
2. Select an integer e such that e is an odd integer greater than 1, less that n, and e and (p−1) (q−1) are relatively prime, i.e.,(e,(p−1)(q−1))=1.
3. Compute an integer d such that (de−1) is evenly divisible by (p−1) (q−1), i.e.,de=1(mod(p−1)(q−l)).
4. The public key is e. n is the modulus.
5. The private key is d.
In this specification, the public and private key pairs will some times be referred to as (e, n) and (d, n), respectively.
The RSA public key e and modulus n are used to encrypt a message m to get cipher message c:c=mee(mod n)and private key d and modulus n are used to decrypt the cipher message c to obtain message m:m=cd(mod n).
The EIGamal cryptosystem is a public key cryptosystem whose security is based on the hardness of the Diffie-Hellman problem. The key generation process is as follows:
1. The server chooses a large prime p and a generator a of the group (Z/(p))* of integers modulo p.
2. The server selects a random integer a with 1≦a≦(p−2) and computes αa mod p.
3. The public key is (p, α, αa) and the private key is a.
For a message m, the enciphered message is a pair of integers (y1, y2) such that y1=αk mod p and y2=m(αa)k mod p, where k is a random integer between 1 and p−2, inclusive. The decryption is performed by computing y1−a·y2 mod p.
For all these cryptosystems and their applications, the basic assumption of security is that a given private key and its associated decrypting process are physically inaccessible except to the holder of the private key. However, there are many applications which require that programs perform decryption on hostile hosts. For example, in applications including e-books and other digital rights management systems, an encrypted document will often be downloaded to the end user with a private key embedded in it. In this scenario, if the decrypting process is standard, an attacker can find the private key, and the decrypted message, by observing this executing process using debugging tools, program tracing tools, and the like.
FIG. 1 shows an example of a typical cryptosystem 10. The cryptosystem 10 comprises a server 11, a communications channel 12, and a client 13. The server 11 comprises a key generation unit 14 and a program P 17 used to encrypt messages m into ciphers c and decrypt ciphers c back to messages m. The key generation unit 14 is used to create a private key 15 and a public key 16. The private key 15 is embedded 18 into the program P 17. When the user is authenticated or otherwise obtains permission from the server 11, the public key 16 and program P 17 are then downloaded to the client 13. The public key 16 is entered into program P 17 by a user. The client comprises the public key 16, program P 17, and application 19.
Cryptosystem applications typically begin with a server generating a private and public key pairs (d, n) and (e, n), respectively. Next a program P 17 is generated which is intended to execute on a client's machine. The private key (d, n) is embedded in P, and part of P's code is able to decrypt cipher messages c encrypted by the public key (e, n).
After P 17 has been installed on the client's machine 13, a message m is created which is intended neither to be publicly acknowledged, nor to be exposed, to the user of the client 13. The message m is encrypted by program P 17 on the server 11 using the public key 16. This encryption process produces a cipher c which is sent to the client 13 via the communications channel 12. The cipher c is decrypted by program P 17 on the client 13 using the embedded private key 18. The decrypted message m is then passed on to the appropriate application 19 in the client 13. The application 19 may for example be an audio player, video player or e-book application.
The message m is not intended to be exposed to the user of the client 13 other than indirectly through the application 19. That is, it is preferable that the message m is played or otherwise processed by the application 19, but that it not be available to an outside observing for copying or transferring to others. However, the decryption of message m causes the states of P 17 to be changed according to the contents of message m. These changes in states may be observed by a hostile user of client 13 using techniques as described above. The observation by the hostile user may expose the embedded private key d and the message m.
In this situation, the client is a legitimate but untrusted party, from the server's point of view. In this scenario, it is desirable to have communication security between the server and the client to protect message c. It is also desirable to have means for protecting the private key d and the decrypted message m from the client.